package com.kevin.Code.Array;

/**
 * @author Vinlee Xiao
 * @Classname MedianofTwoSortedArrays
 * @Description Leetcode 4 寻找两个正序数组的中位数 困难难度
 * @Date 2021/11/11 9:38
 * @Version 1.0
 */
public class MedianofTwoSortedArrays {

    /**
     * 自己思路
     * 题目要求复杂度为log(m+n)
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int len1 = nums1.length;
        int len2 = nums2.length;

        if (len1 + len2 == 1) {
            return len1 == 0 ? nums2[0] : nums1[0];
        }

        int totalLength = len1 + len2;
        int mid = (totalLength) / 2;
        int[] newArr = new int[totalLength];


        int left = 0;
        int right = 0;


        int index = 0;

        int maxValue = Integer.MAX_VALUE;
        while (left < len1 || right < len2) {

            int l = left < len1 ? nums1[left] : maxValue;
            int r = right < len2 ? nums2[right] : maxValue;
            if (l < r) {
                newArr[index] = l;
                left++;
            } else {
                newArr[index] = r;
                right++;
            }
            if (index == mid) {
                break;
            }
            index++;

        }

        double res = 0;
        if (totalLength % 2 == 0) {
            res = (newArr[index] + newArr[index - 1]) * 1.0 / 2;
        } else {
            res = (newArr[index] * 1.0);
        }
        return res;
    }
}
